In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Bajtocki Uniwersytet imienia Bajtazara Gąbki zaczął ostatnio odnosić poważne sukcesy w programowaniu zespołowym. Jego czołowa drużyna - Bajtockie Sępy - w szybkim tempie zdobyła mistrzostwo wszechświata w tej elitarnej dziedzinie. Nie dosyć, że wygrywała ona wszystkie rundy eliminacyjne, to jeszcze na każdym etapie konkursu rozwiązywała zadania na długo przed upływem dostępnego czasu (standardowe 5 godzin). Aby nie nudzić się w czasie, gdy pozostali zawodnicy usiłowali jeszcze rozwiązać jakieś problemy, przez które oni już dawno przebrnęli, Bajtockie Sępy wymyśliły dla rozrywki następującą grę:
Jeden z zawodników bierze kwadratową szachownicę o wymiarach i usuwa z niej (zakrywa) niektóre pola. Drugi z zawodników ma za zadanie ustawić na szachownicy dokładnie wież, przy czym muszą być spełnione następujące warunki:
Ponieważ ta forma gry była dla mistrzów świata zdecydowanie za prosta, zmodyfikowali ją w następujący sposób: dwaj członkowie drużyny, zamiast ustawiać wieże, muszą obliczyć na ile sposobów można ustawić wieże na szachownicy zgodnie z powyższymi zasadami. Liczba ta może być oczywiście bardzo duża - na przykład, na szachownicy, z której nie usunięto żadnych pól, wieże można ustawić na sposobów - jednak co to za problem dla mistrzów świata. Wszystkie obliczenia wykonują oni oczywiście w pamięci, a grę wygrywa ten z graczy, który szybciej poda prawidłową odpowiedź.
Ty prawdopodobnie nie jesteś jeszcze mistrzem świata, więc twoje zadanie będzie łatwiejsze. Wystarczy, że napiszesz program, który stwierdzi, czy liczba sposobów rozstawień wież jest parzysta, czy nieparzysta.
Napisz program, który:
W pierwszym wierszu zapisana jest jedna dodatnia liczba całkowita - liczba przypadków do rozpatrzenia, . Następnie znajduje się opis szachownic, z których każdy wygląda następująco:
W pierwszym wierszu opisującym daną szachownicę znajduje się liczba naturalna - długość i szerokość szachownicy, . W kolejnych wierszach znajdują się opisy kolejnych wierszy szachownicy. W każdym z tych wierszy znajduje się liczb należących do zbioru , pooddzielanych pojedynczymi odstępami. Liczba oznacza, że dane pole zostało usunięte, natomiast , że na danym polu można ustawić wieżę.
Twój program powinien wypisać liczb całkowitych, każdą w osobnym wierszu. Wiersz -ty powinien zawierać dokładnie jedną liczbę - lub - resztę z dzielenia przez liczby sposobów rozstawienia wież na -tej szachownicy, zgodnie z warunkami zadania.
2 3 1 1 1 1 1 0 1 0 1 3 1 0 0 0 1 0 0 0 1poprawną odpowiedzią jest:
1 1
Ilustracja wszystkich możliwości ustawienia wież w pierwszym z przypadków:
Autor zadania: Michał Adamaszek.